// 0-1背包问题：在最优解中，每个物品只有两种可能的情况，即在背包中或者不在背包中
//背包中的该物品数为0或1，因此称为0-1背包问题。 0-1背包完全背包和多重背包
#include <cstdio>
struct Thing {
  int w;
  int v;
} list[101];
int dp[101][1001];
int main() {
  int s, n;  //背包容量和物品总数
  while (scanf("%d%d", &s, &n) != EOF) {
    for (int i = 1; i <= n; i++) {
      scanf("%d%d", &list[i].w, &list[i].v);  //读入每个物品的体积和价值
    }
    for (int i = 0; i <= s; i++) dp[0][i] = 0;  //初始化二维数组
    for (int i = 1; i <= n; i++)  //循环每个物品，执行状态转移方程
    {
      for (int j = s; j >= list[i].w; j--) {
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - list[i].w] + list[i].v);
      }
      for (int j = list[i].w - 1; j >= 0; j--) {
        dp[i][j] = dp[i - 1][j];
      }
    }
    printf("%d\n", dp[n][s]);
  }
  return 0;
}